package main

import (
	"fmt"
	"time"
)

type Node struct {
	next    *Node
	runTime int64
	OnTimer func() int64
}

func (node *Node) InTimer() bool {
	return node.next != nil
}

func (node *Node) RunTime() int64 {
	return node.runTime
}

const (
	SlotShift  = 8
	SlotsCount = 5
	SlotMask   = (1 << SlotShift) - 1
	SlotSize   = (1 << SlotShift) * SlotsCount
)

type Timer struct {
	nodeHeads [SlotSize + 1]*Node
	curTime   int64
}

func NewTimer(curTime int64) *Timer {
	return &Timer{curTime: curTime}
}

func (timer *Timer) CurTime() int64 {
	return timer.curTime
}

func (timer *Timer) Add(runTime int64, node *Node) {
	if node.next != nil {
		panic("added already")
	}
	var idx int32
	dt := runTime - timer.curTime
	if dt < int64(1)<<SlotShift {
		if dt < 0 {
			if runTime < timer.curTime {
				runTime = timer.curTime
				idx = int32(runTime) & SlotMask
			} else {
				idx = SlotSize
			}
		} else {
			idx = int32(runTime) & SlotMask
		}
	} else if dt < int64(1)<<(SlotShift*2) {
		idx = (1 << SlotShift) + (int32(runTime>>SlotShift) & SlotMask)
	} else if dt < int64(1)<<(SlotShift*3) {
		idx = (2 << SlotShift) + (int32(runTime>>(SlotShift*2)) & SlotMask)
	} else if dt < int64(1)<<(SlotShift*4) {
		idx = (3 << SlotShift) + (int32(runTime>>(SlotShift*3)) & SlotMask)
	} else if dt < int64(1)<<(SlotShift*5) {
		idx = (4 << SlotShift) + (int32(runTime>>(SlotShift*4)) & SlotMask)
	} else { // SLOTS_COUNT overflow
		idx = SlotSize
	}
	heads := &timer.nodeHeads
	head := heads[idx]
	if head == nil {
		node.next = node
	} else {
		node.next = head.next
		head.next = node
	}
	heads[idx] = node
	node.runTime = runTime
}

func (timer *Timer) Update(curTime int64) {
	t := timer.curTime
	if curTime < t {
		return
	}
	heads := &timer.nodeHeads
	idx := int32(t) & SlotMask
	for {
		head := heads[idx]
		if head != nil {
			timer.curTime = t
			for {
				heads[idx] = nil
				for node := head.next; ; {
					next := node.next
					node.next = nil
					onTimer := node.OnTimer
					if onTimer != nil {
						nextTime := onTimer()
						if nextTime > 0 {
							timer.Add(t+nextTime, node)
						}
					}
					if node == head {
						break
					}
					node = next
				}
				head = heads[idx]
				if head == nil {
					break
				}
			}
		}
		if t == curTime {
			timer.curTime = t
			return
		}
		t++
		idx = int32(t) & SlotMask
		if idx == 0 {
			i := int32(1)
			for ((t>>(i*SlotShift))&SlotMask) == 0 && i < SlotsCount-1 {
				i++
			}
			for ; i > 0; i-- {
				base := i << SlotShift
				shift := i * SlotShift
				idx1 := base + (int32(t>>shift) & SlotMask)
				head = heads[idx1]
				if head != nil {
					heads[idx1] = nil
					base -= 1 << SlotShift
					shift -= SlotShift
					for node := head.next; ; {
						next := node.next
						idx1 = base + (int32(node.runTime>>shift) & SlotMask)
						if head1 := heads[idx1]; head1 == nil {
							node.next = node
						} else {
							node.next = head1.next
							head1.next = node
						}
						heads[idx1] = node
						if node == head {
							break
						}
						node = next
					}
				}
			}
		}
	}
}

type rand int64

func (rand *rand) rand() int64 {
	r := *rand*6364136223846793005 + 1442695040888963407
	*rand = r
	return int64(r)
}

type state struct {
	rand     rand
	tm       *Timer
	runCount int64
}

func main() {
	t := time.Now().UnixNano()
	var state state
	tm := NewTimer(int64(int32(state.rand.rand())))
	state.tm = tm
	curTime := tm.CurTime()
	for i := 0; i < 100_000; i++ {
		var node Node
		node.OnTimer = func() int64 {
			s := &state
			runTime := node.RunTime()
			curTime := s.tm.CurTime()
			if runTime != curTime {
				panic(fmt.Sprintf("0x%X != 0x%X", runTime, curTime))
			}
			s.runCount++
			return s.rand.rand() & 0x1_ffff
		}
		tm.Add(curTime+(state.rand.rand()&0x1_ffff), &node)
	}
	for i := int64(0); i < 86_400_000; i += 33 {
		tm.Update(curTime + i)
	}
	fmt.Printf("%d, %d ms\n", state.runCount, (time.Now().UnixNano()-t)/1_000_000)
}
